package com.leetcode.algorithm.y22.m08.w2;
import java.util.ArrayList;
import java.util.List;

/**
 * 90. 子集 II
 * 
 * https://leetcode.cn/problems/subsets-ii/
 * 
 * @author jie.deng
 *
 */
class Question0090Solution01 {

	public List<List<Integer>> subsetsWithDup(int[] nums) {
		List<List<Integer>> list = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		int[] cntArr = new int[21]; // -10 <= nums[i] <= 10
		for (int num : nums) {
			cntArr[num + 10]++;
		}
		subsetsWithDup(cntArr, list, 0, path);
		return list;
	}

	private void subsetsWithDup(int[] cntArr, List<List<Integer>> list, int idx, List<Integer> path) {
		int len = cntArr.length;
		if (idx == len) {
			list.add(new ArrayList<>(path));
			return;
		}
		int cnt = cntArr[idx];
		for (int i = 0; i <= cnt; i++) {
			if (i == 0) {
				// 不包含当前元素
				subsetsWithDup(cntArr, list, idx + 1, path);
			} else {
				int loop = i;
				while (loop > 0) {
					// 包含当前元素
					path.add(idx - 10);
					loop--;
				}
				subsetsWithDup(cntArr, list, idx + 1, path);

				loop = i;
				while (loop > 0) {
					path.remove(path.size() - 1);
					loop--;
				}
			}
		}

	}
	
}